package leetcodecompetition.S115;

import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @Author: Siantar
 * @Date: 2023-10-14-23:40
 * @Description: 1.0
 */
public class T100029 {
    public int countSubMultisets(List<Integer> nums, int l, int r) {
        int M = 1000000007;
        Map<Integer, Long> map = new HashMap<>();
        for (int num : nums) {
            Map<Integer, Long> mapT = new HashMap<>();
            if (num <= r) {
                mapT.put(num, 1L);
            }
            for (Map.Entry<Integer, Long> entry : map.entrySet()) {
                int s = entry.getKey() + num;
                if (s <= r) {
                    mapT.put(s, entry.getValue());
                }
            }
            for (Map.Entry<Integer, Long> entry : mapT.entrySet()) {
                int key = entry.getKey();
                map.put(key, (map.getOrDefault(key, 0L) + entry.getValue()) % M);
            }
        }
        long res = 0;
        for (Map.Entry<Integer, Long> entry : map.entrySet()) {
            int key = entry.getKey();
            if (key >= l && key <= r) {
                res = (res + entry.getValue()) % M;
            }
        }
        return (int) res;
    }
}
